package 热题100.子串.最小覆盖子串_76_困难;
/*
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

思路：
        维护子串还是用滑动窗口，当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口
        先统计t中每个字母出现的频次数组charsT[]。
        如果charsN[右指针字母] < charsT[右指针字母] 就说明当前字母出现的频次没达到t中出现的频次，
        此时count可以++，相当于距离t的子串更近了一步
        判断s的子串一定包含t的条件是：
        count == t.length，这是因为只有s子串数组charsN[]的对应字母和t中字母相同且没有超过t中字母次数时，count才会增加。
        比如t中的a出现了三次，而子串中第一次遇到a那么dis++，一直到子串第四次遇到a此时charsN[a] == charsT[a] 那么count就不变化，所以
        count能保证s子串一定包含t。

        右边界是对字母次数数组以及dis增加的，左边界是对字母次数数组以及count减少的，二者交替。
        charsN[] 记录子串所有字母出现的次数，如果左边界移动，那么字母出现次数一定会-1.

        最小区间长度min在左指针刚开始移动的时候来维护

错误1： charsT[]数组统计的s的字符次数
错误2： 直接用下标判断数组，应该使用s.charAt(下标)
错误3： right的循环条件写错了，进入了思维惯性，不是left < right，而是right < s.lenght()
错误4： 第一个剪枝条件少了t == ""
* */
public class Solution {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";
        System.out.println(minWindow(s, t));
    }
    public static String minWindow(String s, String t) {
        if (s == null || t == null || s == "" || t == "" ||s.length() < t.length()){
            return "";
        }
        int[] charsT = new int[128];
        int[] charsN = new int[128];
        // 记录t中每个字符出现的次数
        for (int i = 0; i < t.length(); i ++){
            charsT[t.charAt(i)] ++;
        }
        // 定义左右指针以及字符数量 区间最小值 最小区间开始的地方
        int left = 0, right = 0, count = 0, min = Integer.MAX_VALUE, start = 0;
        // 右指针移动
        while (right < s.length()){
            char r = s.charAt(right);
            // 一直移动到包含t中字符的位置
            if (charsT[r] == 0){
                right ++;
                continue;
            }
            // 比较是否超过该字符在t中的次数 是则+1
            if (charsN[r] < charsT[r]){
                count ++;
            }
            charsN[r] ++;
            right ++;
            while (count == t.length()){
                // 更新最小子串开始的地方
                if (right -left < min){
                    min = right - left;
                    start = left;
                }
                char l = s.charAt(left);
                if (charsT[l] == 0){
                    left ++;
                    continue;
                }
                // 如果左边下标的字母出现在t中了,此时就能退出循环了
                if (charsN[l] == charsT[l]){
                    count --;
                }
                // 该字符次数 -1
                charsN[l] --;
                left ++;
            }
        }
        if (min == Integer.MAX_VALUE){
            return "";
        }
        // 返回s的这一段区间
        return s.substring(start, min + start);
    }
}
